\chapter{数组}

\section{数组}

\subsection{数组（Array）}

数组能够存储一组类型相同的元素，数组在声明时必须指定它的大小（容量），数组的大小是固定的，无法在运行时动态改变。数组通过下标（index）来访问某一位置上的元素，下标从0开始。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int[] arr = new int[5];
\end{lstlisting}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[scale=0.5]
		\draw[-] (0,0) -- (5,0) -- (10,0) -- (15,0) -- (20,0) -- (25,0) -- (25,2.6) -- (20,2.6) -- (15,2.6) -- (10,2.6) -- (5,2.6) -- (0,2.6) -- (0,0);
		\draw[-] (5,0) -- (5,2.6);
		\draw[-] (10,0) -- (10,2.6);
		\draw[-] (15,0) -- (15,2.6);
		\draw[-] (20,0) -- (20,2.6);

		\draw (2.5,1.3) node {arr[0]};
		\draw (7.5,1.3) node {arr[1]};
		\draw (12.5,1.3) node {arr[2]};
		\draw (17.5,1.3) node {arr[3]};
		\draw (22.5,1.3) node {arr[4]};
	\end{tikzpicture}
\end{figure}

如果在声明数组时没有指定数组的大小，那么将根据初始化的元素个数来确定。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int[] arr = {3, 6, 8, 2, 4, 0, 1, 7};
\end{lstlisting}

通过下标可以访问数组中的元素，下标的有效范围是0 $ \sim $ 数组的长度 - 1，如果使用不合法的下标就会导致数组越界。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
System.out.println(arr[0]);		// 3
System.out.println(arr[3]);		// 2
System.out.println(arr[7]);		// 7
\end{lstlisting}

当数组的容量比较大时，可以使用循环来初始化数组。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int[] arr = new int[10];

for(int i = 0; i < 10; i++) {
	arr[i] = i + 1;
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{查找数据}

\begin{lstlisting}[language=Java]
import java.util.Scanner;

public class Search {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.print("Enter the number of elements: ");
		int n = scanner.nextInt();

		int[] arr = new int[n];
		System.out.print("Enter the elements: ");
		for (int i = 0; i < n; i++) {
			arr[i] = scanner.nextInt();
		}

		System.out.print("Enter the key: ");
		int key = scanner.nextInt();
		scanner.close();

		boolean found = false;

		for (int i = 0; i < n; i++) {
			if (arr[i] == key) {
				found = true;
				break;
			}
		}

		if (found) {
			System.out.println(key + " exists.");
		} else {
			System.out.println(key + " not found.");
		}
	}
}	
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Enter the number of elements: 5
Enter the elements: 4 8 9 2 3
Enter the key: 2
2 exists.
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\mybox{最大值/最小值}

\begin{lstlisting}[language=Java]
public class MaxMin {
	public static void main(String[] args) {
		int[] num = {7, 6, 2, 9, 3, 1, 4, 0, 5, 8};
		int n = num.length;
		int max = num[0];
		int min = num[0];

		for (int i = 1; i < n; i++) {
			if (num[i] > max) {
				max = num[i];
			}
			if (num[i] < min) {
				min = num[i];
			}
		}

		System.out.println("Max = " + max);
		System.out.println("Min = " + min);
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Max = 9
Min = 0
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{for-each}

for-each循环是一种更加简洁的for循环，可以用于遍历访问数组中的每一个元素。\\

\mybox{平方和}

\begin{lstlisting}[language=Java]
public class SquareSum {
	public static void main(String[] args) {
		int[] arr = {7, 6, 2, 9, 3};
		int sum = 0;
		for (int elem : arr) {
			sum += elem * elem;
		}
		System.out.println("Square sum = " + sum);
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Square sum = 179
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{二维数组（2-Dimensional Array）}

二维数组由行和列两个维度组成，行和列的下标同样也都是从0开始。在声明二维数组时，需要指定行和列的大小。二维数组可以看成是由多个一维数组组成的，因此二维数组中的每个元素都是一个一维数组。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int[][] arr = new int[3][4];
int[][] arr = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
\end{lstlisting}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|}
			\hline
			arr[0][0] & arr[0][1] & arr[0][2] & arr[0][3] \\
			\hline
			arr[1][0] & arr[1][1] & arr[1][2] & arr[1][3] \\
			\hline
			arr[2][0] & arr[2][1] & arr[2][2] & arr[2][3] \\
			\hline
		\end{tabular}
	}
\end{table}

在初始化二维数组时，为了能够更直观地看出二维数组的结构，可以将每一行单独写在一行中。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int[][] arr = {
	{1, 2, 3, 4},
	{5, 6, 7, 8},
	{9, 10, 11, 12},
};
\end{lstlisting}

对于容量较大的二维数组，可以通过两层循环进行初始化。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int[][] arr = new int[3][4];

for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 4; j++) {
		arr[i][j] = 0;
	}
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{矩阵运算}

\begin{align}\nonumber
	\left[\begin{matrix}
			1 & 3 \\
			1 & 0 \\
			1 & 2 \\
		\end{matrix} \right]
	+
	\left[\begin{matrix}
			0 & 0 \\
			7 & 5 \\
			2 & 1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1+0 & 3+0 \\
			1+7 & 0+5 \\
			1+2 & 2+1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1 & 3 \\
			8 & 5 \\
			3 & 3 \\
		\end{matrix} \right]
\end{align}

\begin{align}\nonumber
	\left[\begin{matrix}
			1 & 3 \\
			1 & 0 \\
			1 & 2 \\
		\end{matrix} \right]
	-
	\left[\begin{matrix}
			0 & 0 \\
			7 & 5 \\
			2 & 1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1-0 & 3-0 \\
			1-7 & 0-5 \\
			1-2 & 2-1 \\
		\end{matrix} \right]
	=
	\left[\begin{matrix}
			1  & 3  \\
			-6 & -5 \\
			-1 & 1  \\
		\end{matrix} \right]
\end{align}

\begin{lstlisting}[language=Java]
public class Matrix {
	public static void main(String[] args) {
		int[][] A = {
				{1, 3},
				{1, 0},
				{1, 2}
		};
		int[][] B = {
				{0, 0},
				{7, 5},
				{2, 1}
		};
		int[][] C = new int[3][2];

		System.out.println("Matrix Addition");
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 2; j++) {
				C[i][j] = A[i][j] + B[i][j];
				System.out.printf("%3d", C[i][j]);
			}
			System.out.println();
		}

		System.out.println("Matrix Subtraction");
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 2; j++) {
				C[i][j] = A[i][j] - B[i][j];
				System.out.printf("%3d", C[i][j]);
			}
			System.out.println();
		}
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Matrix Addition
  1  3
  8  5
  3  3
Matrix Subtraction
  1  3
  -6 -5
  -1  1 
	\end{verbatim}
\end{tcolorbox}

\newpage

\section{字符串}

\subsection{ASCII}

美国信息交换标准代码ASCII（American Standard Code for Information Interchange）一共定义了128个字符。\\

\begin{longtable}{|c|c|c|c|c|c|c|c|}
	\hline
	\textbf{ASCII} & \textbf{字符} & \textbf{ASCII} & \textbf{字符} & \textbf{ASCII} & \textbf{字符}          & \textbf{ASCII} & \textbf{字符}          \\
	\hline
	0              & NUT           & 32             & (space)       & 64             & @                      & 96             & \lstinline|`| \\
	\hline
	1              & SOH           & 33             & !             & 65             & A                      & 97             & a                      \\
	\hline
	2              & STX           & 34             & \text{"}      & 66             & B                      & 98             & b                      \\
	\hline
	3              & ETX           & 35             & \#            & 67             & C                      & 99             & c                      \\
	\hline
	4              & EOT           & 36             & \$            & 68             & D                      & 100            & d                      \\
	\hline
	5              & ENQ           & 37             & \%            & 69             & E                      & 101            & e                      \\
	\hline
	6              & ACK           & 38             & \&            & 70             & F                      & 102            & f                      \\
	\hline
	7              & BEL           & 39             & \text{'}      & 71             & G                      & 103            & g                      \\
	\hline
	8              & BS            & 40             & (             & 72             & H                      & 104            & h                      \\
	\hline
	9              & HT            & 41             & )             & 73             & I                      & 105            & i                      \\
	\hline
	10             & LF            & 42             & *             & 74             & J                      & 106            & j                      \\
	\hline
	11             & VT            & 43             & +             & 75             & K                      & 107            & k                      \\
	\hline
	12             & FF            & 44             & ,             & 76             & L                      & 108            & l                      \\
	\hline
	13             & CR            & 45             & -             & 77             & M                      & 109            & m                      \\
	\hline
	14             & SO            & 46             & .             & 78             & N                      & 110            & n                      \\
	\hline
	15             & SI            & 47             & /             & 79             & O                      & 111            & o                      \\
	\hline
	16             & DLE           & 48             & 0             & 80             & P                      & 112            & p                      \\
	\hline
	17             & DC1           & 49             & 1             & 81             & Q                      & 113            & q                      \\
	\hline
	18             & DC2           & 50             & 2             & 82             & R                      & 114            & r                      \\
	\hline
	19             & DC3           & 51             & 3             & 83             & S                      & 115            & s                      \\
	\hline
	20             & DC4           & 52             & 4             & 84             & T                      & 116            & t                      \\
	\hline
	21             & NAK           & 53             & 5             & 85             & U                      & 117            & u                      \\
	\hline
	22             & SYN           & 54             & 6             & 86             & V                      & 118            & v                      \\
	\hline
	23             & TB            & 55             & 7             & 87             & W                      & 119            & w                      \\
	\hline
	24             & CAN           & 56             & 8             & 88             & X                      & 120            & x                      \\
	\hline
	25             & EM            & 57             & 9             & 89             & Y                      & 121            & y                      \\
	\hline
	26             & SUB           & 58             & :             & 90             & Z                      & 122            & z                      \\
	\hline
	27             & ESC           & 59             & ;             & 91             & [                      & 123            & \{                     \\
			\hline
	28             & FS            & 60             & <             & 92             & $ \backslash $         & 124            & |                      \\
			\hline
	29             & GS            & 61             & =             & 93             & ]                      & 125            & \}                     \\
	\hline
	30             & RS            & 62             & >             & 94             & \lstinline|^| & 126            & \lstinline|~| \\
	\hline
	31             & US            & 63             & ?             & 95             & \_                     & 127            & DEL                    \\
	\hline
\end{longtable}

\vspace{0.5cm}

\mybox{ASCII}

\begin{lstlisting}[language=Java]
public class ASCII {
	public static void main(String[] args) {
		for (int i = 0; i < 128; i++) {
			System.out.println(String.format("%c - %d", i, i));
		}
	}
}
\end{lstlisting}

\vspace{0.5cm}

\subsection{字符串（String）}

一个字符串由若干的字符组成，因此可以使用字符数组表示。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
char[] str = {'p', 'r', 'o', 'g', 'r', 'a', 'm'};
\end{lstlisting}

但是这样的写法比较麻烦，也不容易对字符串进行操作，因此可以使用更为常用的String类来保存字符串。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
String str = "program";
\end{lstlisting}

占位符\%s可以对字符串进行格式化输出操作，通过Scanner类的next()和nextLine()方法可以读取字符串，其中next()只读取到空格为止，而nextLine()会读取到回车为止。\\

\mybox{字符串输入输出}

\begin{lstlisting}[language=Java]
import java.util.Scanner;

public class StringIO {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.print("Enter string 1: ");
		String str1 = scanner.nextLine();
		System.out.println(str1);

		System.out.print("Enter string 2: ");
		String str2 = scanner.next();
		System.out.printf("%s", str2);

		scanner.close();
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Enter string 1: hello world
hello world
Enter string 2: hello world
hello
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\mybox{字符统计}

\begin{lstlisting}[language=Java]
import java.util.Scanner;

public class Frequency {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.print("Enter a string: ");
		String str = scanner.nextLine();
		System.out.print("Character to search: ");
		char c = scanner.next().charAt(0);

		int cnt = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == c) {
				cnt++;
			}
		}

		System.out.printf(
				"\'%c' appears %d times in \"%s\".\n", c, cnt, str
		);
		scanner.close();
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
Enter a string: this is a test
Character to search: t
't' appears 3 times in "this is a test".
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{包装类（Wrapper Class）}

包装类在基本数据类型上做一层包装，使得基本数据类型可以进行互相转换的操作。\\

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|}
			\hline
			\textbf{基本数据类型} & \textbf{包装类型} \\
			\hline
			byte                  & Byte              \\
			\hline
			short                 & Short             \\
			\hline
			int                   & Integer           \\
			\hline
			long                  & Long              \\
			\hline
			float                 & Float             \\
			\hline
			double                & Double            \\
			\hline
			char                  & Character         \\
			\hline
			boolean               & Boolean           \\
			\hline
		\end{tabular}
	}
	\caption{包装类}
\end{table}

将基本数据类型转换为包装类型的过程称为装箱（boxing），反之将包装类型转换为基本数据类型的过程称为拆箱（unboxing）。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
Integer num1 = 123;
int num2 = num1;
\end{lstlisting}

很多时候需要将字符串与基本数据类型进行转换，这时就需要用到包装类的方法。\\

在将基本数据类型转换为字符串的过程中，可以使用String类的valueOf()方法。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
int num = 10;
String str = String.valueOf(num);
\end{lstlisting}

在将字符串转换为基本数据类型的过程中，可以使用包装类的valueOf()或parseXXX()方法。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
Integer num1 = Integer.valueOf("10");
System.out.println(num1);

int num2 = Integer.parseInt("10");
System.out.println(num2);
\end{lstlisting}

需要注意的是，在将字符串转换为基本数据类型时，可能会转换失败。例如将一个非整数的字符串转换为整数，就会抛出NumberFormatException异常。\\

\subsection{字符串内存}

字符串的存储方式与基本数据类型不同，字符串是存储在常量池中的。当使用双引号创建字符串时，会将常量池中已经存在的字符串赋值给该字符串，而不是创建一个新的字符串。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
String s1 = "hello world";
String s2 = "hello world";
\end{lstlisting}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw (-1,-5) rectangle (1,-4);
		\draw (0,-4.5) node {s1/s2};

		\draw (-1.5,-7) rectangle (1.5,-6);
		\draw (0,-6.5) node {"hello world"};
		\draw (0,-7.5) node {常量池};

		\draw[->] (0,-5) -- (0,-6);
	\end{tikzpicture}
\end{figure}

但是，如果通过new关键字创建字符串，就会创建一个新的字符串对象。

\vspace{-0.5cm}

\begin{lstlisting}[language=Java]
String s1 = new String("hello world");
String s2 = new String("hello world");
\end{lstlisting}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw (-4,-5.5) rectangle (-2,-4.5);
		\draw (2,-5.5) rectangle (4,-4.5);
		\draw (-3,-5) node {s1};
		\draw (3,-5) node {s2};

		\draw (-2.7,-7.5) rectangle (-0.3,-6.5);
		\draw (-1.5,-7) node {String对象};
		\draw (0.3,-7.5) rectangle (2.7,-6.5);
		\draw (1.5,-7) node {String对象};

		\draw[->] (-2,-5) -- (-1.5,-6.5);
		\draw[->] (2,-5) -- (1.5,-6.5);

		\draw (-1.5,-9) rectangle (1.5,-10);
		\draw (0,-9.5) node {"hello world"};
		\draw (0,-10.5) node {常量池};

		\draw[->] (-1.5,-7.5) -- (-0.5,-9);
		\draw[->] (1.5,-7.5) -- (0.5,-9);
	\end{tikzpicture}
\end{figure}

在判断两个字符串是否相等时，应该使用equals()方法，而不应该使用==运算符。因为==运算符是判断两个字符串对象的地址是否相同，而equals()方法是判断两个字符串的内容是否相等。\\

\mybox{字符串比较}

\begin{lstlisting}[language=Java]
public class StringCompare {
	public static void main(String[] args) {
		String s1 = new String("hello world");
		String s2 = new String("hello world");
		System.out.println(s1 == s2);
		System.out.println(s1.equals(s2));
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
false
true
	\end{verbatim}
\end{tcolorbox}

\newpage

\section{字符串方法}

\subsection{字符串匹配}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1mm}{
		\begin{tabular}{|l|l|}
			\hline
			\textbf{方法}      & \textbf{功能}                   \\
			\hline
			indexOf()          & 获取字符/字符串首次出现位置     \\
			\hline
			lastIndexOf()      & 获取字符/字符串最后一次出现位置 \\
			\hline
			contains()         & 判断字符串是否包含子串          \\
			\hline
			startsWith()       & 判断字符串是否以指定子串开头    \\
			\hline
			endsWith()         & 判断字符串是否以指定子串结尾    \\
			\hline
			equals()           & 判断字符串是否相等              \\
			\hline
			equalsIgnoreCase() & 判断字符串忽略大小写是否相等    \\
			\hline
			compareTo()        & 字符串比较                      \\
			\hline
		\end{tabular}
	}
\end{table}

\vspace{0.5cm}

\mybox{字符串匹配}

\begin{lstlisting}[language=Java]
public class StringMatch {
	public static void main(String[] args) {
		String str = "Hello World!";

		System.out.println("IndexOf");
		System.out.println(str.indexOf('l'));
		System.out.println(str.indexOf('l', 5));
		System.out.println(str.lastIndexOf('l'));
		System.out.println(str.lastIndexOf('l', 5));

		System.out.println("Contains");
		System.out.println(str.contains("llo"));

		System.out.println("Starts/Ends With");
		System.out.println(str.startsWith("Hell"));
		System.out.println(str.endsWith("ld"));

		System.out.println("Equals");
		System.out.println(str.equals("hello"));
		System.out.println(str.equalsIgnoreCase("hello world!"));

		System.out.println("CompareTo");
		System.out.println(str.compareTo("Hall"));
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
[IndexOf]
2
9
9
3
[Contains]
true
[Starts/Ends With]
true
false
[Equals]
false
true
[CompareTo]
4
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{字符串修改}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1mm}{
		\begin{tabular}{|l|l|}
			\hline
			\textbf{方法} & \textbf{功能}    \\
			\hline
			concat()      & 字符串拼接       \\
			\hline
			toLowerCase() & 转换小写         \\
			\hline
			toUpperCase() & 转换大写         \\
			\hline
			trim()        & 去除首尾空白字符 \\
			\hline
			replace()     & 字符串替换       \\
			\hline
		\end{tabular}
	}
\end{table}

\vspace{0.5cm}

\mybox{字符串修改}

\begin{lstlisting}[language=Java]
import java.util.Locale;

public class StringModify {
	public static void main(String[] args) {
		String str = "Hello World!";

		System.out.println("[Concat]");
		System.out.println(str.concat("!!"));

		System.out.println("[To Lower/Upper Case]");
		System.out.println(str.toLowerCase());
		System.out.println(str.toUpperCase());

		System.out.println("[Trim]");
		System.out.println("   Hello World!\n \t".trim());

		System.out.println("[Replace]");
		System.out.println(str.replace('l', 'L'));
		System.out.println(str.replace("Hello", "Bye"));
	}
}	
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
[Concat]
Hello World!!!
[To Lower/Upper Case]
hello world!
HELLO WORLD!
[Trim]
Hello World!
[Replace]
HeLLo WorLd!
Bye World!
	\end{verbatim}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{字符串分割}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1mm}{
		\begin{tabular}{|l|l|}
			\hline
			\textbf{方法} & \textbf{功能}  \\
			\hline
			substring()   & 字符串截取子串 \\
			\hline
			split()       & 字符串分割     \\
			\hline
		\end{tabular}
	}
\end{table}

\vspace{0.5cm}

\mybox{字符串分割}

\begin{lstlisting}[language=Java]
public class StringSlice {
	public static void main(String[] args) {
		String str = "Hello World!";

		System.out.println("[Substring]");
		System.out.println(str.substring(4));
		System.out.println(str.substring(4, 8));

		System.out.println("[Split]");
		String[] items = str.split(" ");
		for (String item : items) {
			System.out.println(item);
		}
	}
}
\end{lstlisting}

\begin{tcolorbox}
	\mybox{运行结果}
	\begin{verbatim}
[Substring]
o World!
o Wo
[Split]
Hello
World!
	\end{verbatim}
\end{tcolorbox}

\newpage